/*
 * Copyright 北京航空航天大学 @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.linkedlist;

/**
 * <p>
 * 反转单链表
 * 递归/非递归方法
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com
 * 2015年5月17日
 */
public class ReverseLinkedList {

    public ListNode reverseList(ListNode head) {
        //没有元素或者只有一个元素需要直接返回
        if(head==null /*|| head.next==null*/){
            return head;
        }
        //设置哑元节点便于操作
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        //从第二个节点开始遍历
        ListNode cur = head.next;
        //链表的尾节点的next设置为null
        head.next = null;
        while(cur!=null){
            //依次插入遍历过的节点
            ListNode next = cur.next;
            cur.next = dummy.next;
            dummy.next = cur;
            cur = next;
        }
        return dummy.next;
    }

}
